#include <iostream>
#include <vector>
#include <mutex>
using std::cout;
using std::endl;
#include <cassert>


typedef size_t PageID;

//有多少个自由链表
static const size_t Bucket_Num = 208;
//表示单次申请的最大字节数
static const size_t Max_Byte = 256*1024;

static const size_t Package_Num = 129;

static const size_t Pack_Shift = 13;

#ifdef _WIN32
    #include <Windows.h>    // Windows API
    #include <memoryapi.h>  // VirtualAlloc 等函数
#else
    #include <sys/mman.h>   // Linux mmap
    #include <unistd.h>     // Linux sysconf
#endif

// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32 // Windows下的系统调用接口
	void* ptr = VirtualAlloc(0, kpage << Pack_Shift, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
    ptr = mmap(
        nullptr,              // 地址：让内核自动选择
        kpage << Pack_Shift,      // 长度：需要分配的内存大小
        PROT_READ | PROT_WRITE, // 保护：内存可读可写
        MAP_PRIVATE | MAP_ANONYMOUS, // 标志：私有匿名映射
        -1,                   // 文件描述符：-1 表示不关联文件
        0                     // 偏移量：0
    );
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

// 直接去堆上释放空间
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
    // Windows平台使用VirtualFree释放虚拟内存
    // MEM_RELEASE表示释放内存并解除地址空间映射
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    // Linux和类Unix平台使用munmap释放内存映射
    // 注意：munmap需要知道内存块的大小，这里假设ptr指向的内存块开头有大小信息
    // 实际使用时需要根据对应的分配方式调整
    
    // 先获取内存块大小（假设在内存块头部存储了大小信息）
    if (ptr == nullptr) return;
    
    // 假设内存块分配时预留了大小字段（例如在ptr前4/8字节）
    size_t* size_ptr = (size_t*)ptr - 1;
    size_t size = *size_ptr;
    
    // 调用munmap释放内存，需要起始地址和大小
    // 注意：地址必须是mmap返回的地址，且大小必须与分配时一致
    munmap((void*)size_ptr, size + sizeof(size_t));
#endif
}

static void*& ObjNext(void*& obj)
{
    return *(void**)obj;
}


//TC中挂载的
class Freelist{
public:

    void PopRange(void*& start,void*& end,size_t n)
    {
        start = end = _freelist;
        for(int i = 0; i < n-1; i++)
        {
            end = ObjNext(end);
        }
        _freelist = ObjNext(end);
        ObjNext(end) = nullptr;
        _size-=n;
    }
    bool Empty()
    {
        return _freelist==nullptr;
    }
    void push(void* obj)    //收容闲置的空间
    {
        assert(obj);
        //头插入
        ObjNext(obj) = _freelist;
        _freelist = obj;
        ++_size;
    }
    void* pop()         //给出闲置空间进行使用
    {
        //拿出空间来用
        void* obj = _freelist;
        _freelist = ObjNext(obj);
        --_size;
        return obj;
    }
    size_t& getMaxSize()
    {
        return _MaxSize;
    }
    void pushRange(void* start,void* end,size_t size)
    {
        ObjNext(end) = _freelist;
        _freelist = start;
        _size+=size;
    }
    size_t GetSize()
    {
        return _size;
    }
private:
    void* _freelist = nullptr;
    //表示最多可申请多少块空间
    size_t _MaxSize = 1;
    size_t _size = 0;
};



class SizeClass{
public:
    static size_t GetPageNum(size_t size)
    {
        size_t num = GetNum(size);
        size_t pagesize = num*size;

        size_t npage = pagesize >> Pack_Shift;
        if(npage==0)
            npage=1;
        return npage;
    }
    static size_t GetNum(size_t size)
    {
        assert(size > 0);
        size_t Num = Max_Byte/size;
        if(Num > 512)
        {
            Num = 512;
        }
        if(Num < 2)
        {
            Num= 2;
        }
        return Num;
    }
    //获得对齐之后的字节数
    static size_t RoundUP(size_t size)
    {
        assert(size > 0);
        if(size<=128)
        {
            return _RoundUP(size,8);
        }else if(size <= 1024)
        {
            return _RoundUP(size,16);
        }else if(size <= 8*1024)
        {
            return _RoundUP(size,128);
        }else if(size < 64*1024)
        {
            return _RoundUP(size,1024);
        }else if(size < 256*1024){
            return _RoundUP(size,8*1024);
        }else{
            //大于256KB的，那就需要按页向PC申请开辟空间
            return _RoundUP(size,1 << Pack_Shift);
        }
        return -1;
    }
    //根据size，我们来确定在哪一个哈希桶里面
    static size_t Index(size_t size)
    {
        assert(size < Max_Byte);
        static int group_array[4] = { 16, 56, 56, 56 };
        if(size<=128)
        {
            return _index(size,3);
        }else if(size <= 1024)
        {
            return _index(size-128,4)+group_array[0];
        }else if(size <= 8*1024)
        {
            return _index(size-1024,7)+group_array[0]+group_array[1];
        }else if(size < 64*1024)
        {
            return _index(size-8*1024,10)+group_array[0]+group_array[1]+group_array[2];
        }else if(size < 256*1024){
            return _index(size-64*1024,13)+group_array[0]+group_array[1]+group_array[2]+group_array[3];
        }else{
            assert(false);
        }
        return -1;
    }

private:
    //传入要申请空间的大小 以及对齐数
    static size_t _RoundUP(size_t size,size_t num)
    {
        return ((size+num-1) & ~(num-1));
    }
    static inline size_t _index(size_t size,size_t Bit)
    {
        return ((size + (1 << Bit) - 1) >> Bit) - 1;
    }
};


struct Span{
public:
    PageID _pageID = 0;//页号
    void* _freelist = nullptr;//指向span下面挂载的空间

    size_t _n = 0;//当前span块下管理的页数
    size_t _usecount = 0;//分配了多少块空间出去

    bool isUse = false;//默认span块是在PC中的

    size_t _blocksize = 0;

    Span* _prev = nullptr;
    Span* _next = nullptr;
};

class SpanList{
public:
    //判断是不是为空,有没有挂Span
    bool Empty()
    {
        return head->_next == head;
    }
    //删除第一个Span
    Span* popFront()
    {
        Span* front = head->_next;
        //断开连接
        erase(front);
        return front;
    }
    void PushFront(Span* span1)
    {
        insert(Begin(),span1);
    }
    Span* Begin()
    {
        return head->_next;
    }
    Span* End()
    {
        return head;
    }
    SpanList()
    {
        head = new Span;
        head->_next = head;
        head->_prev = head;
    }
    //在pos前面插入
    void insert(Span* pos,Span* ptr)
    {
        assert(pos);
        assert(ptr);

        ptr->_next = pos;
        ptr->_prev = pos->_prev;
        pos->_prev->_next = ptr;
        pos->_prev = ptr;

    }
    //删除pos这个块
    void erase(Span* pos)
    {
        assert(pos);
        assert(pos!=head);

        pos->_prev->_next = pos->_next;
        pos->_next->_prev = pos->_prev;
        pos->_prev = nullptr;
        pos->_next = nullptr;
    }
public:
    //cc中的哈希桶是需要加锁访问的
    std::mutex _mutex;
private:
    Span* head;//哨兵节点
};